In many storage systems, data is stored under encryption utilizing one or more data encryption keys. However, problems can arise when such systems are configured for multiple tenancy. For example, deduplication can be difficult to implement in an efficient manner in some multi-tenant storage systems. Deduplication may generally refer to any of a variety of different processes designed to avoid storing duplicate data items in a storage system. The failure to implement an efficient deduplication process can be wasteful of storage resources, thereby potentially increasing system cost and complexity while also significantly undermining system performance.